#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


int orangesRotting(vector<vector<int>>& grid) {
	return dfs(grid);
}

int dfs(vector<vector<int>>& grid) {
	int orig = 0;
	int bad_orig = 0;
	int ans = -1;
	vector<vector<int>> dir = { {1,0 }, {0, 1},{-1,0},{0,-1} };

	vector<vector<bool>> visit(grid.size(), vector<bool>(grid[0].size(), false));
	queue<pair<int,int>> que;
	for (size_t i = 0; i < grid.size(); i++)
	{
		for (int j = 0; j < grid[0].size(); j++) {
			if (grid[i][j] == 1)orig++;
			if (grid[i][j] == 2) {
				orig++;
				bad_orig++;
				que.push({ i,j });
				visit[i][j] = true;
			}
		}
	}

	if (orig == bad_orig)return 0;
	while (!que.empty())
	{
		int size = que.size();
		for (size_t i = 0; i < size; i++)
		{
			pair<int, int> curr = que.front();
			que.pop();
			for (size_t j = 0; j < 4; j++)
			{
				int curr_x = curr.first + dir[j][0];
				int curr_y = curr.second + dir[j][1];
				if (curr_x >= 0 && curr_x < grid.size() && curr_y >= 0 && curr_y < grid[0].size()) {
					if (!visit[curr_x][curr_y] && grid[curr_x][curr_y] == 1) {
						visit[curr_x][curr_y] = true;
						bad_orig++;
						que.push({ curr_x ,curr_y });
					}
				}

			}


		}
		ans++;
	}
	if (bad_orig < orig)return -1;
	return ans;
}


bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
	vector<int> InDegree(numCourses, 0);
	for (size_t i = 0; i < prerequisites.size(); i++)
	{
		InDegree[prerequisites[i][0]]++;
	}

	queue<int> que;
	for (size_t i = 0; i < InDegree.size(); i++)
	{
		if (InDegree[i] == 0) {
			que.push(i);
			numCourses--;
		}
	}

	while (!que.empty())
	{
		int curr = que.front(); que.pop();
		for (size_t i = 0; i < prerequisites.size(); i++)
		{
			if (prerequisites[i][1] == curr) {
				InDegree[prerequisites[i][0]]--;
				if (InDegree[prerequisites[i][0]] == 0) {
					que.push(prerequisites[i][0]);
					numCourses--;
				}
			}
		}

	}

	if (numCourses == 0)return true;
	return false;

}